# Exercise 1

A->BB->CCB->CCCC
За първата буква 2 варианта, втората буква 2 варианта, ...
2 * 2 * 2 * 2 = 16

# Exercise 2

A->BB->CCB->CCCC
думи с дължина 0: 1
думи с дължина 1: 2
думи с дължина 2: 4
думи с дължина 3: 8
думи с дължина 4: 16
1 + 2 + 8 + 4 + 16 = 1 + 10 + 20 = 31

# Exercise 3

ПРЕЧКА: .^n регулярен ли е?

a. НЕ, балансиране, (^n )^n
b. ?, (^2n
c. ДА, няма цикличност, т.е. краен
d. ДА, a*b
e. ДА, ba*
f. НЕ, a^2n b^n
g. ДА, (aab)*
h. ДА, (aab)+

# Exercise 4

a. ДА, S->A->B-> C->B+C->C+C
b. НЕ, S->A->C->D->B-|
                 -|
              ->B+C-|
           ->B-|
c. НЕ, S->A->D-|
           ->B-|
           ->C-|
d. ДА, S->A->C->D->A
e. НЕ, C->1C не може да породи
f. ДА, C->C+B

# Exercise 5

a. ?
b. ?
c. ЛЯВА РЕКУРСИЯ, A->Aab
d. РАЗЛИЧЕН ЕЗИК, S->dAa->da

# Exercise 6

E->E*E->5*E->5*E+E->5*3+E->...
                  ->5*E+4->...
 ->E+E->E+4->E+E+4->5*3+E+4->...
      ->5*3+E->...

# Exercise 7

a. да, избираме дърво 3 вместо 4
b. не, дървета 1 и 2 не се различават с това
c. да, избираме дърво 1 вместо 2 финално
d. не, никои дървета не се различават с това

# Exercise 8

a. ДА, (00)+, регулярен => безконтекстен
b. ДА, a^n b^n, не рег, да безк
c. НЕ, a^n b^n c^n, не рег, не безк
d. ?
e. ?

# Exercise 9

Г1. n++
    S->aSb->aSbb->abbb
    S->Sb->aSbb->abbb
    m=0
    k=0
    заради S->aSb

Г3. n++
    S->SaS->SaSaS->aaS->aaa
    S->SaS->SaSaS->Saa->aaa

# Exercise 10

S->A1->101
     ->1
     ->C1->01
         ->11
 ->1B->1
     ->1C1->101
          ->111
Думи: 101, 1, 01, 11, 111 ; 5
Дървета: 7
отг) а
